 //
// Created by 86131 on 2023/10/24.
//

#ifndef SHUJUJIEGUO_SEARCHTREE_H
#define SHUJUJIEGUO_SEARCHTREE_H

#endif //SHUJUJIEGUO_SEARCHTREE_H
#include "BinaryTree.h"
class SearchTree : public BinaryTree{
public:
    void insert(int value) override{
        if(root == nullptr){
            root = new TreeNode(value);//如果这个树里面没有一个元素的话，那么就去new一个新节点
            return;
        }
        TreeNode* curr = root;
        while (true) {//递归的非递归定义，遵循着左小右大的原则，使得任意一个节点的左孩子一点小于该节点，然以一个节点的右孩子一定大于该节点
            if(value<curr->val){
                if(curr->left== nullptr){
                    curr->left = new TreeNode(value);
                    return;
                }
                curr = curr->left;
            }else {
                if(value>=curr->val){
                    if(curr->right== nullptr){
                        curr->right = new TreeNode(value);
                        return;
                    }
                    curr = curr->right;
                }
            }
        }
    }

    bool search(int value) override {
        return searchRecursive(root, value);
    }
    TreeNode* get_tree(){
        return root;
    }
private:
    bool searchRecursive(TreeNode* node,int value) {//用递归的方法实现了搜索二叉树，我们给定一个值，他如何去搜索这个值在那里
        if(node== nullptr){return false;}//如果是空的话，那么直接返回flase
        if(node->val==value){return true;}//找到的返回true
        if(value>node->val){ return searchRecursive(node->right,value);}//大了去右树找
        else{return searchRecursive(node->left,value);}//小了去左树找
    }

};